package leetcode;

/**
 * 29. 两数相除
 *
 * @author yujiafan
 * @version 1.0.0
 * @create 2022-12-26
 */
public class LeetCode29 {

    public static int add(int a, int b) {
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    public static int multi(int a, int b) {
        int a1 = isNeg(a) ? negNum(a) : a;
        int b1 = isNeg(b) ? negNum(b) : b;
        int ans = 0;
        int bit = 0;
        while (b1 != 0) {
            if ((b1 & 1) != 0) {
                ans = add(ans,(a1 << bit));
            }
            bit = add(bit, 1);
            b1 = b1 >> 1;
        }
        return isNeg(a) == isNeg(b) ? ans : negNum(ans);
    }

    public static boolean isNeg(int a) {
        return a < 0;
    }

    public static int negNum(int a) {
        return add(1, ~a);
    }

    public static int div(int a, int b) {
        int ans = 0;
        int c = isNeg(a) ? negNum(a) : a;
        int d = isNeg(b) ? negNum(b) : b;
        for (int i = 30; i >= 0; i = minus(i, 1)) {
            int c1 = c >> i;
            if (c1 >= d) {
                ans = ans | (1 << i);
                c = minus(c, multi(d, 1 << i));
            }
        }
        return isNeg(a) == isNeg(b) ? ans : negNum(ans);
    }

    public static int divide(int dividend, int divisor) {
        if (Integer.MIN_VALUE == dividend && Integer.MIN_VALUE == divisor) {
            return 1;
        } else if (Integer.MIN_VALUE == divisor) {
            return 0;
        } else if (Integer.MIN_VALUE == dividend) {
            if(divisor == -1){
                return Integer.MAX_VALUE;
            }
            int c = add(dividend, 1);
            int d = div(c, divisor);
            int temp = minus(dividend, multi(d, divisor));
            return add(d, div(temp, divisor));
        } else {
            return div(dividend, divisor);
        }
    }

    public static void main(String[] args) {
        System.out.println(add(-13, 64));
        System.out.println(minus(1, 3));
        System.out.println(multi(-3, -4));
        System.out.println(div(-64, -7));
        System.out.println(Integer.MIN_VALUE);
        System.out.println(divide(Integer.MIN_VALUE, -1));
        System.out.println(Integer.MIN_VALUE/-1);
    }
}
